﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using TomanuExtensions;
using System.Diagnostics;
using System.Globalization;

namespace RaytracerLib.MathLib.PolynomialFunction
{
    public static class TreeTransforms
    {
        public static Element Simplify(Element a_root, string[] a_sort_parameters = null)
        {
            return Transform(a_root, true, true, false, a_sort_parameters);
        }

        public static Element Expand(Element a_root, bool a_remove_subs, bool a_restore_subs)
        {
            return Transform(a_root, a_remove_subs, a_restore_subs, true);
        }

        private static Element Transform(Element a_root, bool a_remove_subs, bool a_restore_subs, bool a_expand, 
            string[] a_sort_parameters = null)
        {
            if (a_remove_subs)
            {
                a_root = SubToAdd(a_root);
                a_root = MinusToOne(a_root);
            }

            bool more_divs = true;

            for (; ; )
            {
                bool changed = false;

                if (more_divs)
                    a_root = DivToMul(a_root, ref changed, ref more_divs);

                a_root = SimplifyAddZero(a_root, ref changed);
                a_root = SimplifyAddNumbers(a_root, ref changed);
                a_root = SimplifyMulNumbers(a_root, ref changed);
                a_root = SimplifyPow(a_root, ref changed);
                a_root = SimplifyPowZero(a_root, ref changed);
                a_root = SimplifyMulNumbers(a_root, ref changed);
                a_root = SimplifyMulVariables(a_root, ref changed);
                a_root = PowToVariableExponent(a_root, ref changed);

                if (a_expand)
                {
                    a_root = ExpandMulAdd(a_root, ref changed);
                    a_root = ExpandPowAdd(a_root, ref changed);
                    a_root = ExpandPowMul(a_root, ref changed);
                }

                if (changed)
                    continue;

                a_root = SimplifyAddVariables(a_root, ref changed);

                if (!changed)
                    break;
            }

            if (a_sort_parameters != null)
                Sort(a_root, a_sort_parameters);

            if (a_restore_subs)
            {
                a_root = RestoreMinusFromMulMinusOne(a_root);
                a_root = RestoreMinusFromMinusNumber(a_root);

                for (; ; )
                {
                    bool changed = false;

                    a_root = MoveMinusBeforeMul(a_root, ref changed);
                    a_root = RemoveMinusMinus(a_root, ref changed);

                    if (!changed)
                        break;
                }

                for (; ; )
                {
                    bool changed = false;

                    a_root = RestoreSubs(a_root, ref changed);

                    if (changed)
                        continue;

                    a_root = MoveMinusUp(a_root, ref changed);

                    if (!changed)
                        break;
                }

                for (; ; )
                {
                    bool changed = false;

                    a_root = MoveMinusBeforeMul(a_root, ref changed);

                    if (!changed)
                        break;
                }

                a_root = DisplaySort(a_root);
            }

            return a_root;
        }

        private static Element DisplaySort(Element a_root)
        {
            List<MulOperator> muls = new List<MulOperator>();
            foreach (var element in a_root.AllElements)
            {
                MulOperator mul = element as MulOperator;

                if (mul == null)
                    continue;

                muls.Add(mul);
            }

            foreach (var mul in muls)
            {
                NumberSymbol num = mul.Left as NumberSymbol;
                if (num == null)
                    num = mul.Right as NumberSymbol;
                if (num != null)
                {
                    MulOperator group_mul = mul.GroupGrandparent<MulOperator>();

                    if (!Object.ReferenceEquals(group_mul, mul))
                    {
                        a_root = TreeOperations.RemoveSymbol(a_root, num);
                        a_root = TreeOperations.InsertBefore(a_root, group_mul, new MulOperator(), num);
                        continue;
                    }
                }

                num = mul.Right as NumberSymbol;

                if (num == null)
                    continue;

                TreeOperations.SwitchChildren(mul);
            }
              
            return a_root;
        }

        private static Element MinusToOne(Element a_root)
        {
            if (a_root.AllChildren.Count() + 1 < 2)
                return a_root;

            List<MinusOperator> minuses = new List<MinusOperator>();
            foreach (var element in a_root.AllElements)
            {
                MinusOperator minus = element as MinusOperator;

                if (minus == null)
                    continue;

                minuses.Add(minus);
            }

            foreach (var minus in minuses)
            {
                NumberSymbol num = minus.Child as NumberSymbol;
                
                if (num != null)
                {
                    a_root = TreeOperations.Remove(a_root, minus);
                    num.Value = -num.Value;
                }
                else
                {
                    MulOperator mul = new MulOperator
                    (
                        new NumberSymbol(-1),
                        minus.Child
                    );

                    a_root = TreeOperations.ReplaceTree(a_root, minus, mul);
                }
            }

            return a_root;
        }

        private class SortComparer : IComparer<Tuple<int, Element, List<VariableSymbol>>>
        {
            private string[] m_parameters;

            public SortComparer(string[] a_parameters)
            {
                m_parameters = a_parameters;
            }

            public int Compare(Tuple<int, Element, List<VariableSymbol>> a_x, 
                Tuple<int, Element, List<VariableSymbol>> a_y)
            {
                foreach (var param in m_parameters)
                {
                    double exp1 = Constants.DOUBLE_MIN;
                    double exp2 = Constants.DOUBLE_MIN;

                    foreach (var vr in a_x.Item3)
                    {
                        if (!vr.Name.StartsWith(param))
                            continue;

                        if (vr.Exponent > exp1)
                            exp1 = vr.Exponent;
                    }

                    foreach (var vr in a_y.Item3)
                    {
                        if (!vr.Name.StartsWith(param))
                            continue;

                        if (vr.Exponent > exp2)
                            exp2 = vr.Exponent;
                    }

                    if (exp1 == exp2)
                        continue;

                    return Math.Sign(exp1 - exp2);
                }

                return 0;
            }
        }

        private static void Sort(Element a_root, string[] a_parameters)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return;

            var map = new Dictionary<AddOperator, List<Tuple<int, Element, List<VariableSymbol>>>>();

            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                Element mul_group_root;

                MulOperator mul_parent = element.Parent as MulOperator;
                if (mul_parent != null)
                    mul_group_root = mul_parent.GroupGrandparent<MulOperator>();
                else
                    mul_group_root = vr;

                AddOperator add_group_parent = mul_group_root.Parent as AddOperator;

                if (add_group_parent == null)
                    continue;

                add_group_parent = add_group_parent.GroupGrandparent<AddOperator>();

                List<Tuple<int, Element, List<VariableSymbol>>> list1;
                if (map.TryGetValue(add_group_parent, out list1))
                {
                    bool already_done = false;
                    foreach (var el in list1)
                    {
                        if (Object.ReferenceEquals(el.Item1, mul_group_root))
                        {
                            already_done = true;
                            break;
                        }
                    }
                    if (already_done)
                        continue;
                }

                List<VariableSymbol> vars = new List<VariableSymbol>();

                foreach (var el in mul_group_root.AllElements)
                {
                    VariableSymbol vr1 = el as VariableSymbol;

                    if (vr1 != null)
                    {
                        foreach (var vr3 in vars)
                        {
                            if (vr3.Name == vr1.Name)
                                throw new NotImplementedException();
                        }

                        vars.Add(vr1);
                        continue;
                    }

                    MulOperator mul1 = el as MulOperator;

                    if (mul1 != null)
                        continue;

                    NumberSymbol num = el as NumberSymbol;

                    if (num == null)
                        break;
                }

                List<Tuple<int, Element, List<VariableSymbol>>> list;
                if (!map.TryGetValue(add_group_parent, out list))
                {
                    list = new List<Tuple<int, Element, List<VariableSymbol>>>();
                    var tuple = new Tuple<int, Element, List<VariableSymbol>>(0, mul_group_root, vars);
                    list.Add(tuple);
                    map[add_group_parent] = list;
                }
                else
                {
                    var tuple = new Tuple<int, Element, List<VariableSymbol>>(list.Count, mul_group_root, vars);
                    list.Add(tuple);
                }
            }

            SortComparer sort_comparer = new SortComparer(a_parameters);

            foreach (var list in map.Values)
            {
                if (list.Count < 2)
                    continue;

                var org = list.ToList();

                list.Sort(sort_comparer);

                for (int i = 0; i < list.Count; i++)
                {
                    int org_index = list[i].Item1;

                    if (org_index < i)
                        continue;

                    TreeOperations.Switch(list[i].Item2, list[org_index].Item2);
                    var temp = list[i];
                    list[i] = list[org_index];
                    list[org_index] = temp;
                }
            }
        }

        private static Element MoveMinusBeforeMul(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 4)
                return a_root;

            List<MinusOperator> minuses = new List<MinusOperator>();
            foreach (var element in a_root.AllElements)
            {
                MinusOperator minus = element as MinusOperator;

                if (minus == null)
                    continue;

                if (minus.Parent == null)
                    continue;

                minuses.Add(minus);
            }

            foreach (var minus in minuses)
            {
                MulOperator mul = minus.Parent as MulOperator;

                if (mul == null)
                    continue;

                MulOperator mul_root = mul.GroupGrandparent<MulOperator>();
                a_root = TreeOperations.Remove(a_root, minus);
                a_root = TreeOperations.InsertBefore(a_root, mul_root, minus);
                a_changed = true;
            }

            return a_root;
        }

        private class VariableNameSorter : IComparer<VariableSymbol>
        {
            public int Compare(VariableSymbol a_x, VariableSymbol a_y)
            {
                return String.Compare(a_x.Name, a_y.Name);
            }
        }

        private static VariableNameSorter s_variable_name_sorter = new VariableNameSorter();

        // A*B + A*B => 2*A*B
        // A + A => 2*A
        private static Element SimplifyAddVariables(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            var map = new Dictionary<AddOperator, List<Tuple<Element, NumberSymbol, List<VariableSymbol>>>>();

            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                Element mul_group_root;

                MulOperator mul_parent = element.Parent as MulOperator;
                if (mul_parent != null)
                    mul_group_root = mul_parent.GroupGrandparent<MulOperator>();
                else
                    mul_group_root = vr;

                AddOperator add_group_parent = mul_group_root.Parent as AddOperator;

                if (add_group_parent == null)
                    continue;

                add_group_parent = add_group_parent.GroupGrandparent<AddOperator>();

                List<Tuple<Element, NumberSymbol, List<VariableSymbol>>> list1;
                if (map.TryGetValue(add_group_parent, out list1))
                {
                    bool already_done = false;
                    foreach (var el in list1)
                    {
                        if (Object.ReferenceEquals(el.Item1, mul_group_root))
                        {
                            already_done = true;
                            break;
                        }
                    }
                    if (already_done)
                        continue;
                }

                NumberSymbol num = null;
                bool bad_group = false;
                List<VariableSymbol> vars = new List<VariableSymbol>();

                foreach (var el in mul_group_root.AllElements)
                {
                    NumberSymbol num1 = el as NumberSymbol;

                    if (num1 != null)
                    {
                        if (num != null)
                        {
                            bad_group = true;
                            break;
                        }

                        num = num1;
                        continue;
                    }

                    VariableSymbol vr1 = el as VariableSymbol;

                    if (vr1 != null)
                    {
                        foreach (var vr3 in vars)
                        {
                            if (vr3.Name == vr1.Name)
                            {
                                bad_group = true;
                                break;
                            }
                        }

                        if (bad_group)
                            break;

                        vars.Add(vr1);
                        continue;
                    }

                    MulOperator mul1 = el as MulOperator;

                    if (mul1 != null)
                        continue;

                    bad_group = true;
                    break;
                }

                if (bad_group)
                    continue;

                vars.Sort(s_variable_name_sorter);

                var tuple = new Tuple<Element, NumberSymbol, List<VariableSymbol>>(
                    mul_group_root, num, vars);

                List<Tuple<Element, NumberSymbol, List<VariableSymbol>>> list;
                if (!map.TryGetValue(add_group_parent, out list))
                {
                    list = new List<Tuple<Element, NumberSymbol, List<VariableSymbol>>>();
                    list.Add(tuple);
                    map[add_group_parent] = list;
                }
                else
                    list.Add(tuple);
            }

            foreach (var list in map.Values)
            {
                if (list.Count < 2)
                    continue;

                bool break_ij = false;

                do
                {
                    break_ij = false;

                    for (int i = 0; i < list.Count; i++)
                    {
                        var tuple1 = list[i];
                        List<VariableSymbol> list1 = tuple1.Item3;

                        for (int j = i + 1; j < list.Count; j++)
                        {
                            var tuple2 = list[j];
                            List<VariableSymbol> list2 = tuple2.Item3;

                            if (list1.Count != list2.Count)
                                continue;

                            bool not_match = false;

                            Debug.Assert(list1.Intersect(list2).Count() == 0);

                            for (int k = 0; k < list1.Count; k++)
                            {
                                VariableSymbol vr1 = list1[k];
                                VariableSymbol vr2 = list2[k];

                                if (vr1.Name != vr2.Name)
                                {
                                    not_match = true;
                                    break;
                                }

                                if (vr1.Exponent != vr2.Exponent)
                                {
                                    not_match = true;
                                    break;
                                }
                            }

                            if (not_match)
                                continue;

                            a_changed = true;

                            if (tuple1.Item2 != null)
                            {
                                if (tuple2.Item2 != null)
                                    tuple1.Item2.Value += tuple2.Item2.Value;
                                else
                                    tuple1.Item2.Value++;

                                list.RemoveAt(j);
                                a_root = TreeOperations.Remove(a_root, tuple2.Item1);

                                j--;
                            }
                            else if (tuple2.Item2 != null)
                            {
                                if (tuple1.Item2 != null)
                                    tuple2.Item2.Value += tuple1.Item2.Value;
                                else
                                    tuple2.Item2.Value++;

                                list.RemoveAt(i);
                                a_root = TreeOperations.Remove(a_root, tuple1.Item1);

                                break_ij = true;
                            }
                            else
                            {
                                list.RemoveAt(j);
                                a_root = TreeOperations.Remove(a_root, tuple2.Item1);

                                NumberSymbol num = new NumberSymbol(2);
                                MulOperator mul = new MulOperator();

                                a_root = TreeOperations.InsertBefore(a_root, tuple1.Item1, mul, num);

                                tuple1 = new Tuple<Element, NumberSymbol, List<VariableSymbol>>(mul, num, tuple1.Item3);
                                list[i] = tuple1;

                                break_ij = true;
                            }

                            if (break_ij)
                                break;
                        }

                        if (break_ij)
                            break;
                    }
                }
                while (break_ij);
            }

            return a_root;
        }

        // 3 + 3 => 7
        private static Element SimplifyAddNumbers(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            var map = new Dictionary<Operator, List<NumberSymbol>>();

            foreach (var element in a_root.AllElements)
            {
                NumberSymbol num = element as NumberSymbol;

                if (num == null)
                    continue;

                AddOperator parent = num.Parent as AddOperator;

                if (parent == null)
                    continue;

                AddOperator add_group_parent = parent.GroupGrandparent<AddOperator>();

                List<NumberSymbol> list;
                if (!map.TryGetValue(add_group_parent, out list))
                {
                    list = new List<NumberSymbol>();
                    list.Add(num);
                    map[add_group_parent] = list;
                }
                else
                    list.Add(num);
            }

            foreach (var list in map.Values)
            {
                if (list.Count < 2)
                    continue;

                a_changed = true;

                NumberSymbol acc = list.RemoveLast();

                foreach (var num in list)
                {
                    acc.Value += num.Value;
                    a_root = TreeOperations.RemoveSymbol(a_root, num);
                }   
            }

            return a_root;
        }

        // 3 + 0 => 0
        // A + 0 => 0
        private static Element SimplifyAddZero(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            List<NumberSymbol> zeroes = new List<NumberSymbol>();

            foreach (var element in a_root.AllElements)
            {
                NumberSymbol num = element as NumberSymbol;

                if (num == null)
                    continue;
                if (!(num.Parent is AddOperator))
                    continue;

                if (num.Value != 0)
                    continue;

                zeroes.Add(num);
            }

            foreach (var zero in zeroes)
            {
                if (zero.Parent == null)
                    continue;
                if (!(zero.Parent is AddOperator))
                    continue;

                a_root = TreeOperations.RemoveSymbol(a_root, zero);
            }

            a_changed = (zeroes.Count != 0);

            return a_root;
        }

        // 3*4 => 12
        // A*0 => 0
        // A*1 => 1
        private static Element SimplifyMulNumbers(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            var map = new Dictionary<Operator, List<NumberSymbol>>();

            foreach (var element in a_root.AllElements)
            {
                NumberSymbol num = element as NumberSymbol;

                if (num == null)
                    continue;

                MulOperator parent = num.Parent as MulOperator;

                if (parent == null)
                    continue;

                MulOperator mul_group_parent = parent.GroupGrandparent<MulOperator>();

                List<NumberSymbol> list;
                if (!map.TryGetValue(mul_group_parent, out list))
                {
                    list = new List<NumberSymbol>();
                    list.Add(num);
                    map[mul_group_parent] = list;
                }
                else
                    list.Add(num);
            }

            foreach (var kp in map)
            {
                bool done = false;

                var list = kp.Value;

                foreach (var num in list)
                {
                    if (num.Value == 0)
                    {
                        a_root = TreeOperations.ReplaceTree(a_root, kp.Key, num);
                        a_changed = true;
                        done = true;
                        break;
                    }
                    else if (num.Value == 1)
                    {
                        if (list.Count == 1)
                        {
                            a_root = TreeOperations.Remove(a_root, num);
                            a_changed = true;
                            done = true;
                            break;
                        }
                    }
                }

                if (done)
                    continue;

                if (list.Count < 2)
                    continue;

                a_changed = true;

                NumberSymbol acc = list.RemoveLast();

                foreach (var num in list)
                {
                    acc.Value *= num.Value;
                    a_root = TreeOperations.RemoveSymbol(a_root, num);
                }
            }

            return a_root;
        }

        // A*B*A => A^2*B
        private static Element SimplifyMulVariables(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            var map = new Dictionary<Operator, List<VariableSymbol>>();

            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                MulOperator parent = vr.Parent as MulOperator;

                if (parent == null)
                    continue;

                MulOperator mul_group_parent = parent.GroupGrandparent<MulOperator>();

                List<VariableSymbol> list;
                if (!map.TryGetValue(mul_group_parent, out list))
                {
                    list = new List<VariableSymbol>();
                    list.Add(vr);
                    map[mul_group_parent] = list;
                }
                else
                    list.Add(vr);
            }

            foreach (var kp in map)
            {
                var list = kp.Value;

                if (list.Count < 2)
                    continue;

                bool break_ij = false;

                do
                {
                    break_ij = false;

                    for (int i = 0; i < list.Count; i++)
                    {
                        VariableSymbol vr1 = list[i];

                        for (int j = i + 1; j < list.Count; j++)
                        {
                            VariableSymbol vr2 = list[j];

                            Debug.Assert(!Object.ReferenceEquals(vr1, vr2));

                            if (vr1.Name != vr2.Name)
                                continue;

                            a_changed = true;

                            list.RemoveAt(j);
                            j--;

                            vr1.Exponent += vr2.Exponent;

                            a_root = TreeOperations.Remove(a_root, vr2);

                            if (vr1.Exponent == 0)
                            {
                                list.RemoveAt(i);
                                break_ij = true;

                                a_root = TreeOperations.ReplaceTree(a_root, vr1, new NumberSymbol(1));
                            }

                            if (break_ij)
                                break;
                        }

                        if (break_ij)
                            break;
                    }
                }
                while (break_ij);
            }

            return a_root;
        }

        // (A+B) * C => AC + AB
        // (A+B) * (C+D) => A(C+D) + B(C+D)
        private static Element ExpandMulAdd(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 5)
                return a_root;

            List<MulOperator> muls = new List<MulOperator>();
            foreach (var element in a_root.AllElements)
            {
                MulOperator mu = element as MulOperator;

                if (mu == null)
                    continue;

                muls.Add(mu);
            }

            foreach (var mul in muls)
            {
                AddOperator add = null;
                Element second = null;
                add = mul.Left as AddOperator;
                second = mul.Right;
                if (add == null)
                {
                    add = mul.Right as AddOperator;
                    second = mul.Left;
                }
                if (add == null)
                    continue;

                Element A = add.Left;
                Element B = add.Right;

                AddOperator add3 = new AddOperator
                (
                    new MulOperator
                    (
                        A,
                        second
                    ), 
                    new MulOperator
                    (
                        B,
                        second.CloneTree()
                    )
                );

                a_root = TreeOperations.ReplaceTree(a_root, mul, add3);
                a_changed = true;
            }

            return a_root;
        }

        private static Element DivToMul(Element a_root, ref bool a_changed, ref bool a_more_divs)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            List<DivOperator> divs = new List<DivOperator>();
            foreach (var element in a_root.AllElements)
            {
                DivOperator div = element as DivOperator;

                if (div == null)
                    continue;

                divs.Add(div);
            }

            int divs_removed = 0;

            foreach (var div in divs)
            {
                NumberSymbol num = div.Right as NumberSymbol;

                if (num == null)
                    continue;

                num.Value = 1 / num.Value;

                MulOperator mul = new MulOperator
                (
                    div.Left, 
                    num
                );

                divs_removed++;

                a_root = TreeOperations.ReplaceTree(a_root, div, mul);
            }

            a_more_divs = (divs_removed < divs.Count);

            return a_root;
        }

        // A^0 => 1
        // A^1 => A
        // pow(A,2) => A^2
        private static Element PowToVariableExponent(Element a_root, ref bool a_changed)
        {
            List<PowOperator> pows = new List<PowOperator>();
            foreach (var element in a_root.AllElements)
            {
                PowOperator pow = element as PowOperator;

                if (pow == null)
                    continue;

                pows.Add(pow);
            }

            foreach (var pow in pows)
            {
                var num_right = pow.Right as NumberSymbol;

                if (num_right == null)
                    continue;

                if (num_right.Value == 1)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, pow, pow.Left);
                    a_changed = true;
                }

                if (num_right.Value == 0)
                {
                    num_right.Value = 1;
                    a_root = TreeOperations.ReplaceTree(a_root, pow, num_right);
                    a_changed = true;
                }

                VariableSymbol vr_left = pow.Left as VariableSymbol;

                if (vr_left != null)
                {
                    vr_left.Exponent *= num_right.Value;
                    a_root = TreeOperations.ReplaceTree(a_root, pow, vr_left);
                    a_changed = true;
                }

                NumberSymbol num_left = pow.Left as NumberSymbol;

                if (num_left != null)
                {
                    num_left.Value = Math.Pow(num_left.Value, num_right.Value);
                    a_root = TreeOperations.ReplaceTree(a_root, pow, num_left);
                    a_changed = true;
                }
            }

            return a_root;
        }

        // pow(A, 0) => 1
        // pow(A, 1) => A
        // pow(2, 2) => 4
        private static Element SimplifyPow(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            var pows = new List<PowOperator>();

            foreach (var element in a_root.AllElements)
            {
                PowOperator pow = element as PowOperator;

                if (pow == null)
                    continue;

                pows.Add(pow);
            }

            foreach (var pow in pows)
            {
                var exp = pow.Right as NumberSymbol;

                if (exp == null)
                    continue;

                if (exp.Value == 0)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, pow, new NumberSymbol(1));
                    a_changed = true;
                    continue;
                }

                if (exp.Value == 1)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, pow, pow.Left);
                    a_changed = true;
                    continue;
                }

                if (!(pow.Left is NumberSymbol))
                    continue;

                var base_ = pow.Left as NumberSymbol;

                base_.Value = Math.Pow(base_.Value, exp.Value);
                a_root = TreeOperations.RemoveSymbol(a_root, exp);
                a_changed = true;
            }

            return a_root;
        }

        // A^0 => 1
        private static Element SimplifyPowZero(Element a_root, ref bool a_changed)
        {
            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                if (vr.Exponent == 0)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, vr, new NumberSymbol(1));
                    a_changed = true;
                }
            }

            return a_root;
        }

        // pow(A*A, N) => pow(A, n) * pow(A, N) 
        private static Element ExpandPowMul(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 5)
                return a_root;

            // o tego rodzaju grupacch ?
            List<PowOperator> pows = new List<PowOperator>();
            foreach (var element in a_root.AllElements)
            {
                PowOperator pow = element as PowOperator;

                if (pow == null)
                    continue;

                pows.Add(pow);
            }

            foreach (var pow in pows)
            {
                NumberSymbol num_right = pow.Right as NumberSymbol;

                if (num_right == null)
                    continue;

                var mul_left = pow.Left as MulOperator;

                if (mul_left == null)
                    continue;

                Element A = mul_left.Left;
                Element B = mul_left.Right;

                a_root = TreeOperations.ReplaceTree(a_root, pow, mul_left);

                mul_left.Left = pow;
                pow.Left = A;
                pow.Right = num_right;

                PowOperator pow2 = new PowOperator
                (
                    B,
                    num_right.Value
                );

                mul_left.Right = pow2;

                a_changed = true;
            }

            return a_root;
        }

        // pow(A+B, 3) => A^3+3A^2B+3AB^2+B^3
        private static Element ExpandPowAdd(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 5)
                return a_root;

            List<PowOperator> pows = new List<PowOperator>();
            foreach (var element in a_root.AllElements)
            {
                PowOperator pow = element as PowOperator;

                if (pow == null)
                    continue;

                pows.Add(pow);
            }

            foreach (var pow in pows)
            {
                NumberSymbol exp = pow.Right as NumberSymbol;

                if (exp == null)
                    continue;

                if (exp.Value < 0)
                    continue;
                if (exp.Value.Fraction() != 0)
                    continue;

                if (exp.Value == 0)
                    throw new InvalidOperationException();
                if (exp.Value == 1)
                    throw new InvalidOperationException();

                AddOperator add_left = pow.Left as AddOperator;

                if (add_left == null)
                    continue;

                Element A = add_left.Left;
                Element B = add_left.Right;

                int expi = (int)exp.Value;

                int[] exps = MathExtensions.PascalTriangle(expi + 1);

                Element el3 = new PowOperator
                (
                    A.CloneTree(),
                    exp
                );

                for (int i = 1; i < expi; i++)
                {
                    Element pow1;
                    if (expi - i == 1)
                    {
                        pow1 = A.CloneTree();
                    }
                    else
                    {
                        pow1 = new PowOperator
                        (
                            A.CloneTree(),
                            expi - i
                        );

                    }

                    Element pow2;
                    if (i == 1)
                    {
                        pow2 = B.CloneTree();
                    }
                    else
                    {
                        pow2 = new PowOperator
                        (
                            B.CloneTree(),
                            i
                        );
                    }

                    el3 = new AddOperator
                    (
                        el3,
                        new MulOperator
                        (
                            new MulOperator
                            (
                                new NumberSymbol(exps[i]),
                                pow1
                            ),
                            pow2
                        )
                     );
                }

                el3 = new AddOperator
                (
                    el3,
                    new PowOperator
                    (
                        B,
                        expi
                    )
                );

                a_root = TreeOperations.ReplaceTree(a_root, pow, el3);
                a_changed = true;
            }

            return a_root;
        }

        private static Element SubToAdd(Element a_root)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            List<SubOperator> subs = new List<SubOperator>();
            foreach (var element in a_root.AllElements)
            {
                SubOperator sub = element as SubOperator;

                if (sub == null)
                    continue;

                subs.Add(sub);
            }

            foreach (var sub in subs)
            {
                AddOperator add = new AddOperator(sub.Left, new MinusOperator(sub.Right));
                a_root = TreeOperations.ReplaceTree(a_root, sub, add); 
            }

            return a_root;
        }

        private static Element MoveMinusUp(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            List<MinusOperator> minuses = new List<MinusOperator>();
            foreach (var element in a_root.AllElements)
            {
                MinusOperator minus = element as MinusOperator;

                if (minus == null)
                    continue;

                if (minus.Parent == null)
                    continue;

                minuses.Add(minus);
            }


            foreach (var minus in minuses)
            {
                AddOperator add = minus.Child as AddOperator;

                if (add != null)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, minus, add);
                    a_root = TreeOperations.InsertBefore(a_root, add.Left, new MinusOperator());
                    a_root = TreeOperations.InsertBefore(a_root, add.Right, new MinusOperator());
                    a_changed = true;
                    continue;
                }

                SubOperator sub = minus.Child as SubOperator;

                if (sub != null)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, minus, sub);
                    a_root = TreeOperations.InsertBefore(a_root, sub.Left, new MinusOperator());
                    a_root = TreeOperations.InsertBefore(a_root, sub.Right, new MinusOperator());
                    a_changed = true;
                    continue;
                }

                MulOperator mul = minus.Child as MulOperator;

                if (mul != null)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, minus, mul);
                    a_root = TreeOperations.InsertBefore(a_root, mul.Left, new MinusOperator());
                    a_changed = true;
                    continue;
                }

                DivOperator div = minus.Child as DivOperator;

                if (div != null)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, minus, div);
                    a_root = TreeOperations.InsertBefore(a_root, div.Left, new MinusOperator());
                    a_changed = true;
                    continue;
                }

                NumberSymbol num = minus.Child as NumberSymbol;

                if (num != null)
                {
                    a_root = TreeOperations.ReplaceTree(a_root, minus, num);
                    num.Value = -num.Value;
                    a_changed = true;
                    continue;
                }
            }

            return a_root;
        }

        public static Element Diffrentiate(Element a_root, string a_var_name)
        {
            a_root = a_root.CloneTree();
            a_root = TreeOperations.InsertBefore(a_root, a_root, new DifferentiateOperator(a_var_name));

            for (;;)
            {
                bool changed = false;

                List<DifferentiateOperator> diffs = new List<DifferentiateOperator>();
                foreach (var element in a_root.AllElements)
                {
                    DifferentiateOperator diff = element as DifferentiateOperator;

                    if (diff == null)
                        continue;

                    diffs.Add(diff);
                }

                foreach (var diff in diffs)
                {
                    if (diff.Child is MinusOperator)
                    {
                        Element minus_child = (diff.Child as MinusOperator).Child;
                        a_root = TreeOperations.Remove(a_root, diff);
                        a_root = TreeOperations.InsertBefore(a_root, minus_child, diff);
                        changed = true;
                    }
                    else if (diff.Child is AddOperator)
                    {
                        AddOperator add = diff.Child as AddOperator;
                        Element add_left_child = add.Left;
                        Element add_right_child = add.Right;
                        a_root = TreeOperations.Remove(a_root, diff);
                        a_root = TreeOperations.InsertBefore(a_root, add_left_child, diff);
                        a_root = TreeOperations.InsertBefore(a_root, add_right_child, 
                            new DifferentiateOperator(a_var_name));
                        changed = true;
                    }
                    else if (diff.Child is SubOperator)
                    {
                        SubOperator sub = diff.Child as SubOperator;
                        Element sub_left_child = sub.Left;
                        Element sub_right_child = sub.Right;
                        a_root = TreeOperations.Remove(a_root, diff);
                        a_root = TreeOperations.InsertBefore(a_root, sub_left_child, diff);
                        a_root = TreeOperations.InsertBefore(a_root, sub_right_child,
                            new DifferentiateOperator(a_var_name));
                        changed = true;
                    }
                    else if (diff.Child is PowOperator)
                    {
                        PowOperator pow = diff.Child as PowOperator;

                        if (!(pow.Right is NumberSymbol))
                            continue;

                        NumberSymbol exp = pow.Right as NumberSymbol;

                        if (exp.Value < 1)
                            continue;

                        if (exp.Value == 1)
                        {
                            a_root = TreeOperations.RemoveSymbol(a_root, exp);
                            changed = true;
                        }
                        else
                        {
                            MulOperator mul = new MulOperator
                            (
                                exp,
                                new MulOperator
                                (
                                    new DifferentiateOperator
                                    (
                                        diff.Name, 
                                        pow.Left
                                    ),
                                    new PowOperator
                                    (
                                        pow.Left.CloneTree(),
                                        exp.Value - 1
                                    )
                                )
                            );

                            a_root = TreeOperations.ReplaceTree(a_root, diff, mul);
                            changed = true;
                        }
                    }
                    else if (diff.Child is MulOperator)
                    {
                        MulOperator mul = diff.Child as MulOperator;

                        NumberSymbol num = mul.Left as NumberSymbol;
                        Element second = mul.Right;
                        if (num == null)
                        {
                            num = mul.Right as NumberSymbol;
                            second = mul.Left;
                        }

                        if (num != null)
                        {
                            MulOperator mul2 = new MulOperator
                            (
                                num,
                                new DifferentiateOperator
                                (
                                    diff.Name, 
                                    second
                                )
                            );

                            a_root = TreeOperations.ReplaceTree(a_root, diff, mul2);
                            changed = true;
                        }
                        else
                        {
                            AddOperator add = new AddOperator
                            (
                                new MulOperator
                                (
                                    mul.Left,
                                    new DifferentiateOperator
                                    (
                                        diff.Name, 
                                        mul.Right
                                    )
                                ),
                                new MulOperator
                                (
                                    new DifferentiateOperator
                                    (
                                        diff.Name, 
                                        mul.Left.CloneTree()
                                    ),
                                    mul.Right.CloneTree()
                                )
                            );

                            a_root = TreeOperations.ReplaceTree(a_root, diff, add);
                            changed = true;
                        }
                    }
                    else if (diff.Child is VariableSymbol)
                    {
                        VariableSymbol vr = diff.Child as VariableSymbol;

                        if (vr.Name != diff.Name)
                        {
                            a_root = TreeOperations.ReplaceTree(a_root, diff, new NumberSymbol(0));
                            changed = true;
                        }
                        else
                        {
                            if (vr.Exponent == 1)
                            {
                                a_root = TreeOperations.ReplaceTree(a_root, diff, new NumberSymbol(1));
                                changed = true;
                            }
                            else
                            {
                                MulOperator mul2 = new MulOperator
                                (
                                    new NumberSymbol(vr.Exponent),
                                    new VariableSymbol(vr.Name, vr.Exponent - 1)
                                );

                                a_root = TreeOperations.ReplaceTree(a_root, diff, mul2);
                                changed = true;
                            }
                        }
                    }
                    else if (diff.Child is NumberSymbol)
                    {
                        a_root = TreeOperations.ReplaceTree(a_root, diff, new NumberSymbol(0));
                        changed = true;
                    }
                }

                if (!changed)
                    break;
            }

            if (a_root.AllElements.OfType<DifferentiateOperator>().Any())
                throw new InvalidOperationException();

            return a_root;
        }

        private static Element RestoreMinusFromMulMinusOne(Element a_root)
        {
            if (a_root.AllChildren.Count() + 1 < 2)
                return a_root;

            List<NumberSymbol> nums = new List<NumberSymbol>();
            foreach (var element in a_root.AllElements)
            {
                NumberSymbol num = element as NumberSymbol;

                if (num == null)
                    continue;

                if (num.Value != -1)
                    continue;

                nums.Add(num);
            }

            foreach (var num in nums)
            {
                MulOperator mul = num.Parent as MulOperator;

                if (mul == null)
                    continue;

                Element second;
                if (Object.ReferenceEquals(mul.Left, num))
                    second = mul.Right;
                else
                    second = mul.Left;

                MinusOperator minus = new MinusOperator(second);
                a_root = TreeOperations.ReplaceTree(a_root, mul, minus);
            }

            return a_root;
        }

        private static Element RestoreMinusFromMinusNumber(Element a_root)
        {
            List<NumberSymbol> nums = new List<NumberSymbol>();
            foreach (var element in a_root.AllElements)
            {
                NumberSymbol num = element as NumberSymbol;

                if (num == null)
                    continue;

                if (num.Value >= 0)
                    continue;

                nums.Add(num);
            }

            foreach (var num in nums)
            {
                num.Value = -num.Value;
                MinusOperator minus = new MinusOperator();
                a_root = TreeOperations.ReplaceTree(a_root, num, minus);
                minus.Child = num;
            }

            return a_root;
        }

        private static Element RemoveMinusMinus(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            List<MinusOperator> minuses = new List<MinusOperator>();
            foreach (var element in a_root.AllElements)
            {
                MinusOperator minus = element as MinusOperator;

                if (minus == null)
                    continue;

                minuses.Add(minus);
            }

            foreach (var minus in minuses)
            {
                MinusOperator minus2 = minus.Child as MinusOperator;

                if (minus2 == null)
                    continue;

                a_root = TreeOperations.ReplaceTree(a_root, minus, minus2.Child);
                a_changed = true;
            }

            return a_root;
        }

        public static Element UnpackVariables(Element a_root)
        {
            var list = new List<VariableSymbol>();

            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                list.Add(vr);
            }

            foreach (var vr in list)
            {
                if (vr.Exponent == 0)
                    throw new InvalidOperationException();
                else if (vr.Exponent != 1)
                {
                    a_root = TreeOperations.InsertBefore(a_root, vr, new PowOperator(), new NumberSymbol(vr.Exponent));
                    vr.Exponent = 1;
                }
            }

            return a_root;
        }

        public static Element PlugLineEquation(Element a_root, string a_start_name, 
            string a_dir_name, string a_dist_name)
        {
            List<VariableSymbol> vars = new List<VariableSymbol>();
            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                vars.Add(vr);
            }

            foreach (var vr in vars)
            {
                if (vr.Name.Contains('.'))
                    continue;
                if (vr.Name == a_dist_name)
                    continue;

                string start_name = a_start_name + "." + vr.Name;
                string dir_name = a_dir_name + "." + vr.Name;

                Element line;

                if (vr.Exponent != 1)
                {
                    line = new PowOperator
                    (
                        new AddOperator
                        (
                            new VariableSymbol(start_name),
                            new MulOperator
                            (
                                new VariableSymbol(dir_name),
                                new VariableSymbol(a_dist_name)
                            )
                        ),
                        vr.Exponent
                    );
                }
                else
                {
                    line = new AddOperator
                    (
                        new VariableSymbol(start_name),
                        new MulOperator
                        (
                            new VariableSymbol(dir_name),
                            new VariableSymbol(a_dist_name)
                        )
                    );
                }

                a_root = TreeOperations.ReplaceTree(a_root, vr, line);
            }

            return a_root;
        }

        public static void RenameVariables(Element a_root, Dictionary<string, string> a_map)
        {
            foreach (var element in a_root.AllElements)
            {
                VariableSymbol vr = element as VariableSymbol;

                if (vr == null)
                    continue;

                string new_name;

                if (!a_map.TryGetValue(vr.Name, out new_name))
                    continue;

                vr.Name = new_name;
            }
        }

        private static Element RestoreSubs(Element a_root, ref bool a_changed)
        {
            if (a_root.AllChildren.Count() + 1 < 3)
                return a_root;

            List<MinusOperator> minuses = new List<MinusOperator>();
            foreach (var element in a_root.AllElements)
            {
                MinusOperator minus = element as MinusOperator;

                if (minus == null)
                    continue;

                if (minus.Parent == null)
                    continue;

                minuses.Add(minus);
            }

            foreach (var minus in minuses)
            {
                AddOperator add = minus.Parent as AddOperator;

                if (add == null)
                    continue;

                MinusOperator left_minus = add.Left as MinusOperator;
                MinusOperator right_minus = add.Right as MinusOperator;

                if ((left_minus != null) && (right_minus == null))
                {
                    SubOperator sub = new SubOperator
                    (
                        add.Right, 
                        left_minus.Child
                    );

                    a_root = TreeOperations.ReplaceTree(a_root, add, sub);
                    left_minus.Parent = null;
                    a_changed = true;
                }
                else if (right_minus != null)
                {
                    SubOperator sub = new SubOperator
                    (
                        add.Left,
                        right_minus.Child
                    );

                    a_root = TreeOperations.ReplaceTree(a_root, add, sub);
                    right_minus.Parent = null;
                    a_changed = true;
                }
            }

            return a_root;
        }
    }
}
